#ifndef ARC_CACHE_LFU_PART_H
#define ARC_CACHE_LFU_PART_H

#include "ARCCacheNode.h"
#include <list>
#include <map>
#include <memory>
#include <mutex>
#include <unordered_map>

using namespace std;

namespace Cache {

template <typename Key, typename Value> class ArcLFUPart {

public:
    using NodeType = ArcNode<Key, Value>;
    using NodePtr = shared_ptr<NodeType>;
    using NodeMap = unordered_map<Key, NodePtr>;
    using FreqMap = map<size_t, list<NodePtr>>;

    explicit ArcLFUPart(size_t capacity, size_t transformThreshold)
        : capacity_(capacity), ghostcapacity_(capacity), transformThreshold_(transformThreshold), minFreq_(0) {
        initializeLists();
        // cout << "Successful ArcLFUPart construct" << endl;
    }

    bool put(Key k, Value v) {
        if (capacity_ == 0)
            return false;
        lock_guard<mutex> lock(mutex_);
        auto it = mainCache_.find(k);
        if (it == mainCache_.end())
            return addNewNode(k, v);

        return updateExistingNode(it->second, v);
    }

    bool get(Key k, Value &v) {
        lock_guard<mutex> lock(mutex_);
        typename NodeMap::iterator it = mainCache_.find(k);
        if (it != mainCache_.end()) {
            updateNodeFreq(it->second);
            v = it->second->getValue();
            return true;
        }
        return false;
    }

    bool checkGhost(Key k) {
        auto it = ghostCache_.find(k);
        if (it == ghostCache_.end())
            return false;
        removeFromGhost(it->second);
        ghostCache_.erase(it);
        return true;
    }

    void increaseCapacity() {
        capacity_++;
    }

    bool decreaseCapacity() {
        if (capacity_ <= 0)
            return false;
        if (mainCache_.size() == capacity_)
            evictLeastFreq();
        capacity_--;
        return true;
    }

private:
    void initializeLists() {
        ghostHead_ = make_shared<NodeType>();
        ghostTail_ = make_shared<NodeType>();

        ghostHead_->next_ = ghostTail_;
        ghostTail_->prev_ = ghostHead_;
    }

    bool addNewNode(const Key k, const Value v) {
        if (mainCache_.size() >= capacity_)
            evictLeastFreq();
        NodePtr newNode = make_shared<NodeType>(k, v);
        mainCache_[k] = newNode;

        // 将节点添加到频率为1的列表中
        if (freqMap_.find(1) == freqMap_.end())
            freqMap_[1] = list<NodePtr>();
        freqMap_[1].push_back(newNode);
        minFreq_ = 1;
        return true;
    }

    void addToGhost(NodePtr n) {
        n->next_ = ghostTail_;
        n->prev_ = ghostTail_->prev_;

        ghostTail_->prev_->next_ = n;
        ghostTail_->prev_ = n;
        ghostCache_[n->getKey()] = n;
    }

    bool updateExistingNode(NodePtr n, const Value &v) {
        n->setValue(v);
        updateNodeFreq(n);
        return true;
    }

    void updateNodeFreq(NodePtr n) {
        size_t oldFreq = n->getAccCount();
        n->increaseAccCount();
        size_t newFreq = n->getAccCount();

        // 从旧频率列表中移除
        auto &oldList = freqMap_[oldFreq];
        oldList.remove(n);
        if (oldList.empty()) {
            freqMap_.erase(oldFreq);
            if (oldFreq == minFreq_)
                minFreq_ = newFreq;
        }

        // 添加到新频率列表
        if (freqMap_.find(newFreq) == freqMap_.end())
            freqMap_[newFreq] = list<NodePtr>();
        freqMap_[newFreq].push_back(n);
    }

    void evictLeastFreq() {
        if (freqMap_.empty())
            return;

        // 获取最小频率的列表
        auto &minFreqList = freqMap_[minFreq_];
        if (minFreqList.empty())
            return;

        // 移除最少使用的节点
        NodePtr leastNode = minFreqList.front();
        minFreqList.pop_front();

        if (minFreqList.empty()) {
            freqMap_.erase(minFreq_);
            if (!freqMap_.empty())
                minFreq_ = freqMap_.begin()->first;
        }

        // 将节点移到幽灵缓存
        if (ghostCache_.size() >= ghostcapacity_)
            removeOldestGhost();

        addToGhost(leastNode);

        // 移出主缓存
        mainCache_.erase(leastNode->getKey());
    }

    void removeOldestGhost() {
        NodePtr n = ghostHead_->next_;
        if (n != ghostTail_) {
            removeFromGhost(n);
            ghostCache_.erase(n->getKey());
        }
    }

    void removeFromGhost(NodePtr n) {
        n->prev_->next_ = n->next_;
        n->next_->prev_ = n->prev_;
    }

private:
    size_t capacity_;
    size_t ghostcapacity_;
    size_t transformThreshold_;
    size_t minFreq_;
    int a;
    mutex mutex_;

    NodeMap mainCache_;
    NodeMap ghostCache_;
    FreqMap freqMap_;

    NodePtr ghostHead_;
    NodePtr ghostTail_;
};

} // namespace Cache

#endif